#include "left_turn_predicate.h"

bool in_polygon(std::vector<point> &polygon, point &p)
{
   int n = polygon.size();
   if (left_turn(polygon[0], polygon[1], p) < 0 || left_turn(polygon[0], polygon[n - 1], p) > 0)
      return false;

   int lower = 1;
   int higher = n - 1;
   while (higher - lower > 1)
   {
      int middle = (lower + higher) / 2;
      int lt = left_turn(polygon[0], polygon[middle], p);
      if (lt > 0)
         lower = middle;
      else
         higher = middle;
   }

   return !intersect(polygon[0], p, polygon[lower], polygon[higher]);
}